Search results for "Graph toughness"
showing 3 items of 3 documents
Radio Labelings of Distance Graphs
2013
A radio $k$-labeling of a connected graph $G$ is an assignment $c$ of non negative integers to the vertices of $G$ such that $$|c(x) - c(y)| \geq k+1 - d(x,y),$$ for any two vertices $x$ and $y$, $x\ne y$, where $d(x,y)$ is the distance between $x$ and $y$ in $G$. In this paper, we study radio labelings of distance graphs, i.e., graphs with the set $\Z$ of integers as vertex set and in which two distinct vertices $i, j \in \Z$ are adjacent if and only if $|i - j| \in D$.
A dual of 4-regular graph forG × C2n
2003
Abstract A graph is said h-decomposable if its edge-set is decomposable into edge-disjoint hamiltonian cycles. Jha [3] conjectured that if G is a non-bipartite h-decomposable graph on even number of vertices, then G × K2 is h-decomposable. We use the notion of dual graph defined in [4], we prove that if G = Q1,2 ⊕ C3,4 is a 4-regular non-bipartite h-decomposable graph and the dual graphs relative to Q1,2 and C3,4 are connected then G × K 2 and G × C 2n are h-decomposable (where C 2n is an even cycle).
Groups whose prime graph on conjugacy class sizes has few complete vertices
2012
Abstract Let G be a finite group, and let Γ ( G ) denote the prime graph built on the set of conjugacy class sizes of G. In this paper, we consider the situation when Γ ( G ) has “few complete vertices”, and our aim is to investigate the influence of this property on the group structure of G. More precisely, assuming that there exists at most one vertex of Γ ( G ) that is adjacent to all the other vertices, we show that G is solvable with Fitting height at most 3 (the bound being the best possible). Moreover, if Γ ( G ) has no complete vertices, then G is a semidirect product of two abelian groups having coprime orders. Finally, we completely characterize the case when Γ ( G ) is a regular …